data Tree a b = Leaf b | Node a [Tree a b] deriving Eq

treeExample :: Tree Int Bool
treeExample = Node 1 [Leaf True,Node 5 [Leaf False],Node 2 [Leaf True,Leaf True]]

showTree :: (Show a, Show b) => Int -> Tree a b -> String
showTree n (Leaf y)       = replicate n ' ' ++ show y ++ "\n"
showTree n (Node x l)     = replicate n ' ' ++ show x ++ "\n" ++ concatMap (showTree (n+2)) l

instance (Show a, Show b) => Show (Tree a b) where
  show t = showTree 0 t
  
mapTree :: (a -> c) -> (b -> d) -> Tree a b -> Tree c d
mapTree _ g (Leaf y)   = Leaf (g y)
mapTree f g (Node x l) = Node (f x) (map (mapTree f g) l)

foldTree :: (a -> [c] -> c) -> (b -> c) -> Tree a b -> c
foldTree _ g (Leaf y)   = g y
foldTree f g (Node x l) = f x (map (foldTree f g) l)

size :: Tree a b -> Int
size = foldTree (\_ l -> sum l +1) (const 1)

depth :: Tree a b -> Int
depth = foldTree (\_ l -> maximum l +1) (const 0)

allTree :: (a -> Bool) -> (b -> Bool) -> Tree a b -> Bool
allTree pa pb = foldTree (\x l -> pa x && and l) pb

--allTree even id treeExample

anyTree :: (a -> Bool) -> (b -> Bool) -> Tree a b -> Bool
anyTree pa pb = foldTree (\x l -> pa x || or l) pb

--anyTree even id treeExample

toList :: Tree a b -> [Either a b]
toList = foldTree (\x l -> Left x:concat l) ((:[]) . Right)

data NOp = Succ | Add | Mult | If deriving (Eq, Show)

executeNOp :: NOp -> [Int] -> Int
executeNOp Succ [n]     = n+1
executeNOp Add  [m,n]   = m+n
executeNOp Mult [m,n]   = m*n
executeNOp If   [m,n,p] = if m==0 then n else p

type AExpr = Tree NOp Int

expExample :: AExpr
expExample = Node Mult [Leaf 2,Node Add [Leaf 3,Node Succ [Leaf 4]]]

eval :: AExpr -> Int
eval = foldTree executeNOp id